package class08;

import java.util.HashMap;

/**
 * <a href="https://leetcode.cn/problems/implement-trie-prefix-tree/">208. 实现 Trie (前缀树)</a>
 */
public class Code01_TrieTree {

    // 前缀树的结点结构
    public static class Node {
        int pass;
        int end;
        HashMap<Character, Node> nexts;  // 用来记录下一个结点的信息

        public Node() {
            pass = 0;
            end = 0;
            nexts = new HashMap<>();
        }
    }

    // 前缀树数据结构
    public static class Trie {
        // 根节点
        Node root;

        public Trie() {
            root = new Node();
        }

        // 往前缀树中添加字符串
        public void insert(String s) {
            // 如果字符串为空或是长度为0直接退出
            if (s == null || s.isEmpty()) {
                return;
            }
            char[] str = s.toCharArray();  // 将字符串转为char类型方便操作
            Node p = root;
            p.pass++;  // 有字符串进来，根节点pass加1
            for (char ch : str) {
                // 如果字符不在当前结点的表中，则去创建该字符的结点
                if (!p.nexts.containsKey(ch)) {
                    p.nexts.put(ch, new Node());
                }
                p = p.nexts.get(ch);  // 移动到下一个字符
                p.pass++;  // pass要加1，表示有一个字符通过
            }
            p.end++;  // 添加完后，需要在最后一个字符的位置end加1，表示存入了一个字符串
        }

        // 查找某个字符串加入过多少次
        public int search(String s) {
            if (s == null || s.isEmpty()) {
                return 0;
            }
            char[] str = s.toCharArray();
            Node p = root;
            for (char ch : str) {
                if (!p.nexts.containsKey(ch)) {
                    return 0;
                }
                p = p.nexts.get(ch);
            }
            return p.end;
        }

        // 删除某个字符串
        public void delete(String s) {
            if (s == null || s.isEmpty() || search(s) == 0) {
                return;
            }
            char[] str = s.toCharArray();
            Node p = root;
            p.pass--;
            for (char ch : str) {
                // 如果当某个字符的pass为0，那么直接将当前结点删除
                if (--p.nexts.get(ch).pass == 0) {
                    p.nexts.remove(ch);
                    return;
                }
                p = p.nexts.get(ch);
            }
            p.end--;
        }

        // 某个字符串前缀出现多少次
        public int prefix(String s) {
            if (s == null || s.isEmpty()) {
                return 0;
            }
            char[] str = s.toCharArray();
            Node p = root;
            for (char ch : str) {
                if (!p.nexts.containsKey(ch)) {
                    return 0;
                }
                p = p.nexts.get(ch);
            }
            return p.pass;
        }
    }

    // 暴力正确程序
    public static class Right {

        private HashMap<String, Integer> box;

        public Right() {
            box = new HashMap<>();
        }

        public void insert(String word) {
            if (!box.containsKey(word)) {
                box.put(word, 1);
            } else {
                box.put(word, box.get(word) + 1);
            }
        }

        public void delete(String word) {
            if (box.containsKey(word)) {
                if (box.get(word) == 1) {
                    box.remove(word);
                } else {
                    box.put(word, box.get(word) - 1);
                }
            }
        }

        public int search(String word) {
            if (!box.containsKey(word)) {
                return 0;
            } else {
                return box.get(word);
            }
        }

        public int prefixNumber(String pre) {
            int count = 0;
            for (String cur : box.keySet()) {
                if (cur.startsWith(pre)) {
                    count += box.get(cur);
                }
            }
            return count;
        }
    }

    // for test
    public static String generateRandomString(int strLen) {
        char[] ans = new char[(int) (Math.random() * strLen) + 1];
        for (int i = 0; i < ans.length; i++) {
            int value = (int) (Math.random() * 6);
            ans[i] = (char) (97 + value);
        }
        return String.valueOf(ans);
    }

    // for test
    public static String[] generateRandomStringArray(int arrLen, int strLen) {
        String[] ans = new String[(int) (Math.random() * arrLen) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = generateRandomString(strLen);
        }
        return ans;
    }

    public static void main(String[] args) {
        int arrLen = 100;
        int strLen = 20;
        int testTimes = 100000;
        for (int i = 0; i < testTimes; i++) {
            String[] arr = generateRandomStringArray(arrLen, strLen);
            Trie trie1 = new Trie();
            Right right = new Right();
            for (int j = 0; j < arr.length; j++) {
                double decide = Math.random();
                if (decide < 0.25) {
                    trie1.insert(arr[j]);
                    right.insert(arr[j]);
                } else if (decide < 0.5) {
                    trie1.delete(arr[j]);
                    right.delete(arr[j]);
                } else if (decide < 0.75) {
                    int ans1 = trie1.search(arr[j]);
                    int ans3 = right.search(arr[j]);
                    if (ans1 != ans3) {
                        System.out.println("Oops!");
                    }
                } else {
                    int ans1 = trie1.prefix(arr[j]);
                    int ans3 = right.prefixNumber(arr[j]);
                    if (ans1 != ans3) {
                        System.out.println(ans1 - ans3);
                        System.out.println("Oops!");
                    }
                }
            }
        }
        System.out.println("finish!");
    }

}
